/**
 * 188. 买卖股票的最佳时机IV
 */
public class Exerciser8 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        k = Math.min(k,n / 2); // 这里如果 k这个交易次数大于数组长度的二分之一的话，就不能交易k次，最多只能交易n/2次
        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];
        int INF = 0x3f3f3f3f; // int的最大值的一半
        for(int j = 0;j < k;j++) {
            f[0][j] = g[0][j] = -INF;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(int i = 1;i < n;i++) {
            for(int j = 0;j <= k;j++) {
                f[i][j] = Math.max(f[i - 1][j],g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j],f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        // 在 g[n - 1][j] 中寻找最大值
        int ret = 0;
        for(int j = 0;j <= k;j++) {
            ret = Math.max(ret,g[n - 1][j]);
        }
        return ret;
    }
}
